package com.ddf.datastructure.sort;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * 希尔排序是为了解决插入排序如果较小的元素都排在后面，而我们又是按照从小到大的方式排序，
 * 那么必然会造成过多的移位操作，希尔排序是对插入排序的一种优化；
 * 它的核心思想是对一个未排序的数组进行对半切分，然后在切分的数组里进行跳序比较，所以也叫缩小增量排序
 * 它的最优时间复杂度为O(n)，最差则为O(n²),一般介于n的1.3到2平方之间
 *
 * @author dongfang.ding
 * @date 2019/6/27 15:20
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {30, 15, 18, 17, 12, 15, 14, 13};
        int[] sort = swapSort(arr);
        System.out.println("排序前： " + Arrays.toString(arr));
        System.out.println("排序后： " + Arrays.toString(sort));
        sort = insertSort(arr);
        System.out.println("排序后： " + Arrays.toString(sort));
    }


    /**
     * 希尔排序
     *
     *
     *  30, 15, 18, 17, 12, 15, 14, 13
     *
     *  交换法：=========================================================
     *  按照数组长度每次都对半拆分，下面详细推演一下该算法的步骤
     *
     *  1. gap = 8 / 2 = 4, 每4个比较交换一次,数组溢出则一次循环结束，然后循环gap+1次
     *      第1次数组内循环,从0开始数4个，逆序就交换
     *          [0]和[4]比较: 12, 15, 18, 17, 30, 15, 14, 13
     *          [4]和[8]比较: 超出数组长度，跳出循环
     *      第2次数组内循环
     *          [1]和[5]比较: 12, 15, 18, 17, 30, 15, 14, 13
     *          [5]和[9]比较: 超出数组长度，跳出循环
     *      第3次数组内循环
     *          [2]和[6]比较: 12, 15, 14, 17, 30, 15, 18, 13
     *          [6]和[10]比较: 超出数组长度，跳出循环
     *      第4次数组内循环
     *          [3]和[7]比较: 12, 15, 14, 13, 30, 15, 18, 17
     *          [7]和[11]比较: 超出数组长度，跳出循环
 *          第5次数组内循环
     *          [4]和[8]比较: 超出数组长度，跳出循环
     *      循环次数 > gap 跳出外循环
     *
     *  2. gap = 4 / 2 = 2, 每2个比较交换一次,数组溢出则一次循环结束，然后循环gap+1次
     *      第1次数组内循环，[0]开始每次数2个，逆序就交换
     *          [0]和[2]比较: 12, 15, 14, 13, 30, 15, 18, 17
     *          [2]和[4]比较: 12, 15, 14, 13, 30, 15, 18, 17
     *          [4]和[6]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [6]和[8]比较: 超出数组长度，跳出循环
     *      第2次数组内循环，[1]开始每次数2个，逆序就交换
     *          [1]和[3]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [3]和[5]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [5]和[7]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [7]和[9]比较: 超出数组长度，跳出循环
     *      第3次数组内循环，[2]开始每次数2个，逆序就交换
     *          [2]和[4]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [3]和[5]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [5]和[7]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [7]和[9]比较: 超出数组长度，跳出循环
     *      循环次数 > gap 跳出外循环
     *
     *  3. gap = 2 / 2 = 1， 每1个比较交换一次,数组溢出则一次循环结束，然后循环gap+1次
     *      第1次数组内循环，从[0]开始每次数1个，逆序就交换
     *          [0]和[1]比较: 12, 15, 14, 13, 18, 15, 30, 17
     *          [1]和[2]比较: 12, 14, 15, 13, 18, 15, 30, 17
     *          [2]和[3]比较: 12, 14, 15, 13, 18, 15, 30, 17
     *          [3]和[4]比较: 12, 14, 13, 15, 18, 15, 30, 17
     *          [4]和[5]比较: 12, 14, 13, 15, 15, 18, 30, 17
     *          [5]和[6]比较: 12, 14, 13, 15, 15, 18, 30, 17
     *          [6]和[7]比较: 12, 14, 13, 15, 15, 18, 17, 30
     *          [7]和[8]比较: 超出数组长度，跳出循环
     *      第2次数组内循环，从[1]开始每次数1个，逆序就交换
     *          [1]和[2]比较: 12, 13, 14, 15, 15, 18, 17, 30
     *          [2]和[3]比较: 12, 13, 14, 15, 15, 18, 17, 30
     *          [3]和[4]比较: 12, 13, 14, 15, 15, 18, 17, 30
     *          [4]和[5]比较: 12, 13, 14, 15, 15, 18, 17, 30
     *          [5]和[6]比较: 12, 13, 14, 15, 15, 17, 18, 30
     *          [6]和[7]比较: 12, 13, 14, 15, 15, 17, 18, 30
     *          [7]和[8]比较: 超出数组长度，跳出循环
     *      循环次数 > gap 跳出外循环
     *
     *  4. gap拆分成1之后循环完成则，排序完成
     *
     *  交换法：=========================================================
     *
     * @author dongfang.ding
     * @date 2019/6/27 15:20
     */
    public static int[] swapSort(int[] arr) {
        // 拷贝数组，不改变原数组的值
        int[] dest = Arrays.copyOf(arr, arr.length);
        int temp;
        // 数组切分方式,每次对半切分
        for (int gap = dest.length / 2; gap > 0; gap /= 2) {
            // 从[0]开始按照下面循环规则两两替换，一直循环到从[gap]开始找
            for (int i = 0; i <= gap; i ++) {
                // 数组切分好之后，数组内按照gap跳着两两比较，发现逆序就交换
                for (int j = i; j < dest.length - gap; j += gap) {
                    if (dest[j] > dest[j + gap]) {
                        temp = dest[j];
                        dest[j] = dest[j + gap];
                        dest[j + gap] = temp;
                    }
                }
            }
        }
        return dest;
    }


    /**
     * 移位法（插入排序）的排序步骤
     *
     * 30, 15, 18, 17, 12, 15, 14, 13
     * 按照数组长度每次都对半拆分，下面详细推演一下该算法的步骤
     * 1. gap = 8 / 2 = 4, 从[4]开始往后的元素依次和与它之前间隔gap个位置的元素进行插入排序比较
     *      gap内循环，从gap开始循环到数组最后一个元素
     *
     *      第一次循环，待插入元素i = gap = 4 < 数组长度, [4]=12，12为待插入元素
     *          插入排序步骤
     *          12和[4-gap= 0]移位： 30, 15, 18, 17, 30, 15, 14, 13
     *          12和[0-gap=-4]越界，跳出循环
     *          将待插入元素替换到换位的角标[4-gap] 12, 15, 18, 17, 30, 15, 14, 13
     *
     *      第二次循环， i = gap + 1 = 5 < 数组长度, [5] = 15, 15为待插入元素
     *          15和[5-gap= 1]不需要移位: 12, 15, 18, 17, 30, 15, 14, 13
     *          15和[1-gap=-3]移位: 跳出循环
     *
     *      第三次循环， i = gap + 2 = 6 < 数组长度, [6] = 14, 14为待插入元素
     *          14和[6-gap= 2]移位: 12, 15, 18, 17, 30, 15, 18, 13
     *          14和[2-gap=-2]越界，跳出循环，
     *          将待插入元素插入到[6-gap]位 12, 15, 14, 17, 30, 15, 18, 13
     *      第四次循环，i = gap + 3 = 7 < 数组长度, [7] = 13, 13为待插入元素
     *          13和[7-gap= 3]移位: 12, 15, 14, 17, 30, 15, 18, 17
     *          13和[3-gap=-1]数组越界，跳出循环，
     *          将13插入到[7-gap]: 12, 15, 14, 13, 30, 15, 18, 17
     *
     *      第五次循环条件不满足，i = gap + 8 = 8 > 数组长度
     *
     * 2. gap = 4 / 2 = 2, 从[2]开始往后的元素依次和与它之前间隔gap个位置的元素进行插入排序比较
     *      第一次循环，i = gap = 2 < 数组长度, [2] = 14, 14为待插入元素
     *          14和[2-gap= 0]不需要移位： 12, 15, 14, 13, 30, 15, 18, 17
     *          14和[0-gap=-2]: 跳出循环
     *
     *      第二次循环， i = gap + 1 = 3 < 数组长度, [3] = 13, 13为待插入元素
     *          13和[3-gap= 1]移位: 12, 15, 14, 15, 30, 15, 18, 17
     *          13和[1-gap=-1]: 跳出循环
     *          将13插入到[3-gap]: 12, 13, 14, 15, 30, 15, 18, 17
     *
     *      第三次循环， i = gap + 2 = 4 < 数组长度, [4] = 30, 30为待插入元素
     *          30和[4-gap= 2]不需要移位: 12, 13, 14, 15, 30, 15, 18, 17
     *          30和[2-gap= 0]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          30和[0-gap=-2]：跳出循环
     *
     *      第四次循环，i = gap + 3 = 5 < 数组长度, [5] = 15, 15为待插入元素
     *          15和[5-gap= 3]不需要移位: 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[3-gap= 1]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[1-gap=-1]越界： 跳出循环
     *
     *      第五次循环，i = gap + 4 = 6 < 数组长度, [6] = 18, 18为待插入元素
     *          18和[6-gap= 4]不需要移位: 12, 13, 14, 15, 30, 15, 18, 17
     *          18和[4-gap= 2]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          18和[2-gap= 0]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          18和[0-gap=-2]越界，跳出循环
     *
     *      第六次循环，i = gap + 5 = 7 < 数组长度, [7] = 17, 17为待插入元素
     *          17和[7-gap= 5]不需要移位: 12, 13, 14, 15, 30, 15, 18, 17
     *          17和[5-gap= 3]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          17和[3-gap= 1]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          17和[1-gap=-1 ]越界，跳出循环
     *      第七次循环条件不满足,i = gap + 6 = 8 > 数组长度
     *
     *
     * 3. gap = 2 / 2 = 1, 从[1]开始往后的元素依次和与它之前间隔gap个位置的元素进行插入排序比较
     *      第一次循环，i = gap = 1 < 数组长度, [1] = 12, 12为待插入元素
     *          12和[1-gap= 0]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          12和[0-gap=-1]越界， 跳出循环
     *
     *      第二次循环， i = gap + 1 = 2 < 数组长度, [2] = 14, 14为待插入元素
     *          14和[2-gap= 1]不需要移位: 12, 13, 14, 15, 30, 15, 18, 17
     *          14和[1-gap= 0]不需要移位: 12, 13, 14, 15, 30, 15, 18, 17
     *          14和[0-gap=-1]越界，跳出循环
     *
     *      第三次循环， i = gap + 2 = 3 < 数组长度, [3] = 15, 15为待插入元素
     *          15和[3-gap= 2]不需要移位: 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[2-gap= 1]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[1-gap= 0]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[0-gap=-1]越界，跳出循环
     *
     *      第四次循环，i = gap + 3 = 4 < 数组长度, [4] = 30, 30为待插入元素
     *          30和[4-gap= 3]移位:        12, 13, 14, 15, 30, 15, 18, 17
     *          30和[3-gap= 2]不需要移位:   12, 13, 14, 15, 30, 15, 18, 17
     *          30和[2-gap= 1]不需要移位:   12, 13, 14, 15, 30, 15, 18, 17
     *          30和[1-gap= 0]不需要移位:   12, 13, 14, 15, 30, 15, 18, 17
     *          30和[0-gap=-2]越界，跳出循环
     *
     *      第五次循环，i = gap + 4 = 5 < 数组长度, [5] = 15, 15为待插入元素
     *          15和[5-gap= 4]移位: 12, 13, 14, 15, 30, 30, 18, 17
     *          15和[4-gap= 3]不需要移位： 12, 13, 14, 15, 30, 30, 18, 17
     *          15和[3-gap= 2]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[2-gap= 1]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[1-gap= 0]不需要移位： 12, 13, 14, 15, 30, 15, 18, 17
     *          15和[0-gap=-1]越界，跳出循环
     *          将待插入元素15插入到[5-gap]： 12, 13, 14, 15, 15, 30, 18, 17
     *
     *      第六次循环，i = gap + 5 = 6 < 数组长度, [6] = 18, 18为待插入元素
     *          18和[6-gap=5]移位: 12, 13, 14, 15, 15, 30, 30, 17
     *          18和[5-gap=4]不需要移位: 12, 13, 14, 15, 15, 30, 30, 17
     *          18和[4-gap= 3]不需要移位： 12, 13, 14, 15, 15, 30, 30, 17
     *          18和[3-gap= 2]不需要移位： 12, 13, 14, 15, 15, 30, 30, 17
     *          18和[2-gap= 1]不需要移位： 12, 13, 14, 15, 15, 30, 30, 17
     *          18和[1-gap= 0]不需要移位： 12, 13, 14, 15, 15, 30, 30, 17
     *          18和[0-gap=-1]越界，跳出循环
     *          将待插入元素18插入到[6-gap]： 12, 13, 14, 15, 15, 18, 30, 17
     *
     *      第七次循环，i = gap + 6 = 7 < 数组长度, [7] = 17, 17为待插入元素
     *          17和[7-gap=6]移位: 12, 13, 14, 15, 15, 18, 30, 30
     *          17和[6-gap=5]移位: 12, 13, 14, 15, 15, 18, 30, 30
     *          17和[5-gap=4]不需要移位: 12, 13, 14, 15, 15, 18, 30, 30
     *          17和[4-gap= 3]不需要移位： 12, 13, 14, 15, 15, 18, 30, 30
     *          17和[3-gap= 2]不需要移位： 12, 13, 14, 15, 15, 18, 30, 30
     *          17和[2-gap= 1]不需要移位： 12, 13, 14, 15, 15, 18, 30, 30
     *          17和[1-gap= 0]不需要移位： 12, 13, 14, 15, 15, 18, 30, 30
     *          17和[0-gap=-1]越界，跳出循环
     *          将待插入元素17插入到[7-gap]： 12, 13, 14, 15, 15, 18, 17, 30
     *
     *      第八次循环条件不满足,i = gap + 6 = 8 > 数组长度
     *
     *  4. gap=1不能再对半分，跳出循环，正好排序完成
     *
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        // 拷贝数组，不改变原数组的值
        int[] dest = Arrays.copyOf(arr, arr.length);
        // 数组切分方式,每次对半切分
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从gap位置开始循环，分别和之前与它相对应gap位置的元素进行插入排序
            for (int i = gap; i < dest.length; i ++) {
                int insertVal = dest[i];
                int j = i;
                // 注意这里的比较是insertVal < dest[j - gap],因为是从后往前赋值的，所以前面的越大，越要往移动
                while (j - gap >= 0 && insertVal < dest[j - gap]) {
                    dest[j] = dest[j - gap];
                    j -= gap;
                }
                if (insertVal != dest[j]) {
                    dest[j] = insertVal;
                }
            }
        }
        return dest;
    }
}
